#include <iostream>
#include <vector>
using namespace std;

const int max_board_size = 64;

struct SubGraph
{
  int x;
  int y;
  int s;

  SubGraph( int _x, int _y, int _s ): x(_x), y(_y), s(_s) {}
  SubGraph() {}
};

struct Board
{
  unsigned long long pos[max_board_size];
  int length_of_side; //边长
  int leavings; //剩余
  int count; //子图的数量
  int& best_count;
  vector<SubGraph> graphes;

  Board( int length, int& _best_count ) : best_count( _best_count ), graphes( length * length )
  {
    this->length_of_side = length;
    this->leavings = length * length;
    this->count = 0;
    memset( pos, 0x0, sizeof( pos ) );
  }

  //把坐标在(x,y)且边长为s的子图分割出来
  inline bool test( const SubGraph& g )
  {
    unsigned long long flag = 1;
    flag = (flag << ( g.x + g.s )) - (flag << g.x);
    if( ( pos[g.y] & flag ) != 0 ) return false;
    if( ( pos[g.y + g.s - 1] & flag ) != 0 ) return false;
    return true;
  }

  inline void cut( const SubGraph& g )
  {
    unsigned long long flag = 1;
    flag = (flag << ( g.x + g.s )) - (flag << g.x);  
    for( int i = g.y; i < g.y + g.s; i++ )
    {
      pos[i] |= flag;
    }
    leavings -= g.s * g.s;
    SubGraph& g0 = graphes[count++];
    g0.s = g.s;
    g0.x = g.x;
    g0.y = g.y;
  }

  inline void tie()
  {
    SubGraph& g = graphes[--count];
      
    unsigned long long flag = 1;
    flag = (flag << ( g.x + g.s )) - (flag << g.x);
    flag = ~flag;
    for( int i = g.y; i < g.y + g.s; i++ )
    {
      pos[i] &= flag;
    }    
    leavings += g.s * g.s;
  }

  void split( int size )
  {
    if( count >= best_count )
    {
      return;
    }
    
    if( size == 1 || leavings == 0 )
    {
      if( best_count > count + leavings )
      {
        best_count = count + leavings;
        cout << "SLOVE: " << best_count << endl;
      }
      return;
    }

    int max_fill = leavings / ( size * size );
    max_fill = std::min( max_fill, best_count - count );

    int begin = count;

    SubGraph g;
    g.s = size;
    for( g.x = length_of_side - size; g.x >= 0 && count - begin < max_fill; g.x-- )
    {
      for( g.y = length_of_side - size; g.y >= 0 && count - begin < max_fill; g.y-- )
      {
        if( test( g ) )
        {
          cut( g );
        }
      }
    }

    split( size - 1 );
    while( count > begin )
    {
      tie();
      split( size - 1 );
    }
  }
};

void slove( int n )
{
  int solution = n * n + 1;
  int start = ( n % 2 == 0 ) ? n / 2 : n / 2 + 1;
  for( int i = start; i < n; i++ )
  {
    Board t( n, solution );
    t.cut( SubGraph( 0, 0, i ) );
    for( int j = 0; j < i / ( n - i ); j++ )
    {
      t.cut( SubGraph( j * ( n - i ), i, n - i ) );
      t.cut( SubGraph( i , j * ( n - i ), n - i ) ); 
    }
    t.split( n - i );
  }
}

int main()
{
  int cases = 0;
  cin >> cases;
  while( cases-- )
  {
    int n = 0;
    cin >> n;
    slove( n );
  }
}
